#include <iostream>
using namespace std;

struct node
{ int info;
  node *left;
  node *right;
};

node* maketree(int x, node* p, node *q)
{ node * r = new node;
  r->info = x;
  r->left = p;
  r->right = q;
  return r;
}

void preOrder(node * p)
{ if(p!=NULL)
  { cout << p->info << " ";
    preOrder(p->left);
    preOrder(p->right); 
  }
}

void inOrder(node * p)
{ if(p!=NULL)
  { inOrder(p->left);
    cout << p->info << " ";
    inOrder(p->right); 
  }
}

void postOrder(node * p)
{ if(p!=NULL)
  { postOrder(p->left);
    postOrder(p->right); 
    cout << p->info << " ";
  }
}

int nodeCnt(node *p)
{ if(p==NULL) return 0;
  return 1 + nodeCnt(p->left) + nodeCnt(p->right); 
}

int heigth(node *p)
{ if(p==NULL) return 0;
  return 1+max(heigth(p->left),heigth(p->right)); 
}



int main()
{ node *p, *q, *r; 

  p = maketree(15,NULL,NULL);
  p = maketree(70,p,NULL);
  q = maketree(5,NULL,NULL);
  q = maketree(65,q,NULL);
  p = maketree(50,p,q);
  
  q = maketree(10,NULL,NULL);
  q = maketree(80,NULL,q);
  r = maketree(25,NULL,NULL);
  r = maketree(85,r,NULL);
  q = maketree(30,q,r);
  
  node * root = maketree(60,p,q);
         
//  preOrder(root); cout << " K-L-D" << endl;
//  inOrder(root);  cout << " L-K-D" << endl;   
//  postOrder(root);  cout << " L-D-K" << endl;   
   
  cout << "Nodes: " << nodeCnt(root) << endl; 
  cout << "Heigth: " << heigth(root) << endl; 
   
         
  return 0;
}    
